#include <iostream>

struct ListNode
{
   ListNode(int val = 0, ListNode* next = nullptr, \
	       ListNode* prev = nullptr)
      :_next(next), _prev(prev), _val(val)
   { }

   ListNode* _next;
   ListNode* _prev;
   int _val;
};

class List
{
public:
   List()
      :_dummy_head(new ListNode()), _tail(nullptr), _size(0)
   {
      _dummy_head->_next = _dummy_head->_prev = _dummy_head;
      _tail = _dummy_head;
   }

   void push_back(int val)
   {
      ListNode* newNode = new ListNode(val);
      _tail->_next = newNode;
      newNode->_prev = _tail;
      _tail = newNode;
      _tail->_next = _dummy_head;
      _dummy_head->_prev = _tail;
      ++_size;
   }

   void push_front(int val)
   {
      ListNode* newNode = new ListNode(val);
      newNode->_next = _dummy_head->_next;
      newNode->_prev = _dummy_head;
      _dummy_head->_next = newNode;
      ++_size;
   }

   void debug()
   {
      int n = _size;
      ListNode* curNode = _dummy_head->_next;
      while (n--)
      {
	 std::cout << curNode->_val << " ";
	 curNode = curNode->_next;
      }
   }

   ~List()
   {
      delete _dummy_head;
   }

private:
   ListNode* _dummy_head;
   ListNode* _tail;
   size_t _size;
};

int main()
{
   List l;
   l.push_back(10);
   l.push_back(12);
   l.push_front(11);
   l.push_front(22);
   l.debug();
   return 0;
}
